//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
//
// 示例 1:
//
// 输入: "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//
//
// 示例 2:
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//
//
// 示例 3:
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
// Related Topics 哈希表 双指针 字符串 Sliding Window
// 👍 4080 👎 0

package com.beikai.springbootleetcodedemo.demo01.leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new LongestSubstringWithoutRepeatingCharacters().new Solution();
        int abcabcbb = solution.lengthOfLongestSubstring2("pwwkew");
        System.out.println(abcabcbb);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String s) {

            // 使用set作为一个滑动窗口，用来保存不重复的字符串  (注意这个滑块中的元素是不重复的,而且也是无序的,主要用来比较右坐标下一个字符是否与已经在滑块中存在了)
            Set<Character> result = new HashSet<Character>();
            // 设置滑动模块 右边界
            int right = -1, stringSize = 0;
            // 获取字符串长度
            int length = s.length();
            // 便利,从第一个字符串开始
            for (int i = 0; i < length; i++) {
                // 判断是否是第一个位置,如果不是,则删除活动窗口最左边记录,表示窗口向右移动一位
                if (i != 0) {
                    result.remove(s.charAt(i - 1));
                }
                // 移动第二个指针,即滑块右边界 右边界长度不低于字符串长度,并且是滑动窗口中部不包含的字符
                while (right + 1 < length && !result.contains(s.charAt(right + 1))) {
                    result.add(s.charAt(right + 1));
                    right++;
                    //System.out.println("当左边界是 " + s.charAt(i) + " 时,滑动窗口中的记录是 : " + JSONObject.toJSONString(result) + " 此时 右边界坐标是 : " + right);
                }
                // 判断当前滑块的长度是是否是历史最大
                stringSize = Math.max(stringSize, right - i + 1);
            }

            return stringSize;

        }

        public int lengthOfLongestSubstring2(String s) {
            // 其实用的也是滑动窗口 模式 , flag 作为滑动窗口的左侧, i作为滑动窗口的右侧
            // 设置遍历的位置
            int i = 0;
            // 设置 滑动窗口的左侧
            int flag = 0;
            // 设置 临时用来存储 字符串长度
            int length = 0;
            // 存储 窗口的最大值
            int result = 0;
            // 遍历字符串
            while (i < s.length()) {
                char c = s.charAt(i);
                //每次遍历 获取左窗口右侧指定字符串第一次出现的位置
                int pos = s.indexOf(c,flag);
                // 如果第一次出现的位置 小于当前遍历时字符串出现的位置,说明当前位置之前已经有重复的字符,需要计算位置
                if (pos < i) {
                    // 字符串长度赋值给 result ,如果不重复的字符串的长度大于已有的字符串长度
                    if (length > result) {
                        result = length;
                    }
                    // 判断当前剩余的长度是否小于已有的最长的不重复字符串长度 ,如果是,返回最高长度
                    if (result >= s.length() - pos - 1) {
                        return result;
                    }
                    // 计算当前位置与 滑动窗口左侧第一次出现的位置的距离
                    length = i - pos - 1;
                    // 窗口向右移动一位
                    flag = pos + 1;
                }
                //
                length++;
                i++;

                System.out.println("i : " + i + " flag : " + flag + " length : " + length + " result : " + result + " pos : " + pos);
            }
            return length;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}